\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb,graphicx,url}
\usepackage{fullpage}


% Old Stuff
%%\oddsidemargin=0.15in
%%\evensidemargin=0.15in
%%\topmargin=-.5in
%%\textheight=9in
%%\textwidth=6.25in

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.2in { {\bf CS390 Computational Game Theory and Mechanism Design}
     	 \hfill #2 }
       \vspace{4mm}
       \hbox to 6.2in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.2in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\handout}[3]{\heading{#1}{#2}{Instructor:
Jing Chen}{Teaching Assistant: Tao Xiao}{Handout #1: #3}}

\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}
\handout{4}{July 8, 2013}{Problem Set 3}

%This course is an undergraduate introduction to computational game theory, with emphasis on mechanism design.

\textbf{Due by Monday, July 15, 8am.}

\paragraph{Problem 1 (10pt).} (NRTV07, Exercise 17.1.) Suppose that we modify Pigou's example so that the lower edge has cost function $c_2(x) = (x/n)^d$ for some $d\geq 1$. What is the price of anarchy of the resulting selfish routing network when $n$ goes to infinity, as a function of $d$? What does the price of anarchy become when $d$ goes to infinity? (That is, first compute the PoA for any fixed $d$ with $n\rightarrow +\infty$, and then compute the limit of this function as $d\rightarrow +\infty$.)

\paragraph{Problem 2 (10pt).} (NRTV07, Exercise 19.9.) Prove that in any Shapley network design game, the price of anarchy can never exceed $n$, the number of players.

\paragraph{Problem 3 (10pt).} (NRTV07, Exercise 17.3.) Consider minimizing the following objective function in the scheduling game with $n$ players and $n$ machines: for any pure strategy profile $s$, $f(s) = \sum_i c_i(s)$, and for any mixed strategy profile $\sigma$, $f(\sigma) = \mathbb{E}_{s\thicksim \sigma} f(s)$. Compute the price of anarchy, taking into consideration all mixed NEs.

%
%\paragraph{Problem 2 (10pt).} %122ps.pdf 5
%Consider the following two-state game. In the first stage, player 1 chooses $a\in [0,3]$ and pays player 2 $a/9$ (so that player 1 gets a utility of $-a/9$ and player 2 gets a utility of $a/9$. In the second stage, players 1 and 2 play a simultaneous move game which provides them with the additional utility shown below. What is the subgame perfect equilibrium? What is player 1's equilibrium utility?
%
%\begin{center}
%\begin{tabular}{c|c|c|}
%  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
%\multicolumn{1}{c}{} & \multicolumn{1}{c}{$\ L\ $} & \multicolumn{1}{c}{$\ R\ $}  \\ \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $U$                  & $1+a, 0$                     & $0, 1$                     \\ [1ex] \cline{2-3}
% & \multicolumn{1}{|c|}{} & \multicolumn{1}{c|}{}                     \\ [-1.5ex]
%  $D$                  & $0, 1$                     & $1, 0$                     \\ [1ex] \cline{2-3}
%\end{tabular}
%\end{center}

%M. J. Osborne and A. Rubinstein. {\em A course in game theory.} MIT Press, 1994.
%
%N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds). {\em Algorithmic game theory.} Cambridge University Press, 2007. (Available at \url{http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf}.)

\end{document}








